package E_2024;

import java.util.LinkedList;
import java.util.Queue;

/*
题目描述
    网络信号经过传递会逐层衰减，且遇到阻隔物无法直接穿透，在此情况下需要计算某个位置的网络信号值。注意:网络信号可以绕过阻隔物
    array[m][n] 的二维数组代表网格地图
    array[i][j]=0代表i行j列是空旷位置;
    array[i][j]=x(x为正整数)代表i行j列是信号源，信号强度是x;
    array[i][j]=-1代表i行j列是阻隔物.
    信号源只有1个，阻隔物可能有0个或多个
    网络信号衰减是上下左右相邻的网格衰减 1
    现要求输出对应位置的网络信号值。
输入描述
    输入为三行，第一行为 m、n，代表输入是一个mxn的数组。
    第二行是一串 m xn 如个用空格分隔的整数
        每连续n个数代表一行，再往后 n个代表下一行，以此类推。对应的值代表对应的网格是空矿位置，还是信号源，还是阻隔物。
    第三行是i、j，代表需要计算 array[i][j]的网络信号值。
    注意:此处i和j均从 0 开始，即第一行i 为 0
输出描述
    输出对应位置的网络信号值，如果网络信号未覆盖到，也输出0。
    一个网格如果可以途径不同的传播衰减路径传达
例：
    https://pic4.zhimg.com/v2-b997839a0a4017802cf07784f208970f_1440w.jpg
 */
public class E_200_10 {
    public static void main(String[] args) {
        String x = "0 0 0 -1 0 0 0 0 0 0 0 0 -1 4 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0";
        System.out.println(ans(in(x,6,5),1,4));
    }
    public static int[][] in(String str, int n, int m){
        int[][] arr = new int[n][m];
        String[] split = str.split(" ");
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < m; k++) {
                arr[i][k] = Integer.parseInt(split[index++]);
            }
        }
        return arr;
    }
    // 转换为最短路径问题
    public static int ans(int[][] arr, int i, int j){
        int max = 0;
        int maxi = 0;
        int maxj = 0;
        for (int o = 0; o < arr.length; o++) {
            for (int p = 0; p < arr[o].length; p++) {
                if (max < arr[o][p]) {
                    max = arr[o][p];
                    maxi = o;
                    maxj = p;
                }
            }
        }
        Queue<Integer[]> queue = new LinkedList<>();
        queue.add(new Integer[]{maxi,maxj,max});
        while (!queue.isEmpty()){
            Integer[] poll = queue.poll();
            if (poll[0] == i && poll[1] == j) return poll[2];
            arr[poll[0]][poll[1]] = -1;
            if (poll[0] + 1 < arr.length && arr[poll[0]+1][poll[1]] != -1)
                queue.add(new Integer[]{poll[0]+1, poll[1], poll[2]-1});
            if (poll[0] - 1 >= 0 && arr[poll[0]-1][poll[1]] != -1)
                queue.add(new Integer[]{poll[0]-1, poll[1], poll[2]-1});
            if (poll[1] + 1 < arr[0].length && arr[poll[0]][poll[1]+1] != -1)
                queue.add(new Integer[]{poll[0], poll[1]+1, poll[2]-1});
            if (poll[1] - 1 >= 0 && arr[poll[0]][poll[1]-1] != -1)
                queue.add(new Integer[]{poll[0], poll[1]-1, poll[2]-1});
        }
        return 0;
    }// 转换为最短路径问题
    public static int ans1(int[][] arr, int i, int j){
        int max = 0;
        int maxi = 0;
        int maxj = 0;
        for (int o = 0; o < arr.length; o++) {
            for (int p = 0; p < arr[o].length; p++) {
                if (max < arr[o][p]) {
                    max = arr[o][p];
                    maxi = o;
                    maxj = p;
                }
            }
        }
        Queue<Integer[]> queue = new LinkedList<>();
        queue.add(new Integer[]{i,j,0});
        while (!queue.isEmpty()){
            Integer[] poll = queue.poll();
            if (poll[0] == maxi && poll[1] == maxj) return max - poll[2];
            arr[poll[0]][poll[1]] = -1;
            if (poll[0] + 1 < arr.length && arr[poll[0]+1][poll[1]] != -1)
                queue.add(new Integer[]{poll[0]+1, poll[1], poll[2]+1});
            if (poll[0] - 1 >= 0 && arr[poll[0]-1][poll[1]] != -1)
                queue.add(new Integer[]{poll[0]-1, poll[1], poll[2]+1});
            if (poll[1] + 1 < arr[0].length && arr[poll[0]][poll[1]+1] != -1)
                queue.add(new Integer[]{poll[0], poll[1]+1, poll[2]+1});
            if (poll[1] - 1 >= 0 && arr[poll[0]][poll[1]-1] != -1)
                queue.add(new Integer[]{poll[0], poll[1]-1, poll[2]+1});
        }
        return 0;
    }
}
